// 思路： 将数组分成若干个子数组，每个子数组进行归并排序
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
// 稳定性：稳定
// 适用场景：数据量较大
// 不适用于数据量较小的情况
function mergeSort(arr) {
    if(arr.length <= 1) return arr
    let mid = Math.floor(arr.length / 2)
    let left = mergeSort(arr.slice(0, mid))
    let right = mergeSort(arr.slice(mid))
    return merge(left, right)
}

function merge(left, right) {
    let result = []
    let leftIndex = 0
    let rightIndex = 0
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex])
            leftIndex++
        } else {
            result.push(right[rightIndex])
            rightIndex++
        }
    }
    if (leftIndex < left.length) {
        return result.concat(left.slice(leftIndex))
    }
    if (rightIndex < right.length) {
        return result.concat(right.slice(rightIndex))
    }
    return result
}

const arr = [5, 3, 8, 4, 2];
console.log(mergeSort(arr));